package top.lshaci.learning.algorithm;

import java.util.Arrays;

/**
 * CocktailSort
 * <p>
 * 鸡尾酒排序
 * <p>
 * 鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含2个小循环，
 * 第1个小循环从左向右比较并交换元素，
 * 第2个小循环从右向左比较并交换元素。
 *
 * @author liangxu
 */
public class CocktailSort {

    public static void sort(int[] array) {
        for (int i = 0; i < array.length / 2; i++) {
            // 有序标记, 每一轮的初始值都是 true
            boolean isSorted = true;
            // 奇数轮, 从左向右比较和交换
            for (int j = i; j < array.length - 1 - i; j++) {
                int tmp = array[j];
                if (tmp > array[j + 1]) {
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    // 有元素交换, 所以不是有序的, 标记变为false
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
            // 在偶数轮之前, 将isSorted重新标记为true
            isSorted = true;
            for (int j = array.length - 1 - i; j > i; j--) {
                int tmp = array[j - 1];
                if (tmp > array[j]) {
                    array[j - 1] = array[j];
                    array[j] = tmp;
                    // 有元素交换, 所以不是有序的, 标记变为false
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
        sort(array);
        System.err.println(Arrays.toString(array));
    }
}
